import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by zhourh on 2018/8/8.
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

 _______6______
 /              \
 ___2__          ___8__
 /      \        /      \
 0      _4       7       9
 /  \
 3   5
 示例 1:

 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 输出: 6
 解释: 节点 2 和节点 8 的最近公共祖先是 6。
 示例 2:

 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 输出: 2
 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

 */
public class LowestCommonAncestorOfBinarySearchTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node8 = new TreeNode(8);
        TreeNode node0 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node9 = new TreeNode(9);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        root.left = node2;
        root.right = node8;
        node2.left = node0;
        node2.right = node4;
        node8.left = node7;
        node8.right = node9;
        node4.left = node3;
        node4.right = node5;


        System.out.println(new LowestCommonAncestorOfBinarySearchTree().lowestCommonAncestor3(root, node2, node8).val);
        System.out.println(new LowestCommonAncestorOfBinarySearchTree().lowestCommonAncestor3(root, node2, node4).val);


    }

    // 当二叉树不是搜索树的情况，只能使用该方式
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = searchPath(root, p, null);
        List<TreeNode> qPath = searchPath(root, q, null);

        if (pPath == null || pPath.isEmpty() || qPath == null || qPath.isEmpty()) {
            return root;
        }


        for (int i = pPath.size() - 1; i >= 0; i--) {
            if (qPath.contains(pPath.get(i))) {
                return pPath.get(i);
            }
        }

        return root;
    }

    private List<TreeNode> searchPath(TreeNode currentNode, TreeNode targetNode, List<TreeNode> prePath) {
        List<TreeNode> ans = new ArrayList<>();
        if (prePath != null) {
            ans.addAll(prePath);
        }

        ans.add(currentNode);

        if (currentNode.val == targetNode.val) {
            return ans;
        }

        if (currentNode.left != null) {
            List<TreeNode> leftResult = searchPath(currentNode.left, targetNode, ans);
            if (leftResult != null) {
                return leftResult;
            }
        }

        if (currentNode.right != null) {
            List<TreeNode> rightResult = searchPath(currentNode.right, targetNode, ans);
            if (rightResult != null) {
                return rightResult;
            }
        }

        return null;
    }

    // 利用二叉搜索树的特点，使用递归求解
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > root.val && q.val > root.val) {
            // 两个结点均在目标结点的右边，将目标结点降级到右子树
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            // 两个结点均在目标结点的左边，将目标结点降级到右子树
            return lowestCommonAncestor(root.left, p, q);
        } else {
            // 两个结点分布在两边，或某个结点已经是目标结点
            return root;
        }
    }

    // 利用二叉搜索树的特点，使用非递归求解
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        while (true) {
            if (p.val > root.val && q.val > root.val) {
                // 两个结点均在目标结点的右边，将目标结点降级到右子树
                root = root.right;
            } else if (p.val < root.val && q.val < root.val) {
                // 两个结点均在目标结点的左边，将目标结点降级到右子树
               root = root.left;
            } else {
                // 两个结点分布在两边，或某个结点已经是目标结点
                break;
            }
        }

        return root;

    }
}
